|
In mathematics, a natural number ''n'' is a Blum integer if ''n = p×q'' is a semiprime for which ''p'' and ''q'' are distinct prime numbers congruent to 3 mod 4.〔Joe Hurd, Blum Integers (1997), retrieved 17 Jan, 2011 from http://www.gilith.com/research/talks/cambridge1997.pdf〕 That is, ''p'' and ''q'' must be of the form 4''t''+3, for some integer ''t''. Integers of this form are referred to as Blum primes.〔Goldwasser, S. and Bellare, M. ("Lecture Notes on Cryptography" ). Summer course on cryptography, MIT, 1996-2001〕 This means that the factors of a Blum integer are Gaussian primes with no imaginary part. The first few Blum integers are :21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ... Blum integers were named for computer scientist Manuel Blum. ==Properties== Given ''n'' = ''p''×''q'' a Blum integer, ''Q''''n'' the set of all quadratic residues modulo n, and ''a'' ∈ ''Q''''n''. Then:〔 *''a'' has precisely four square roots modulo ''n'', exactly one of which is also in ''Q''''n'' *The unique square root of ''a'' in ''Q''''n'' is called the ''principal square root'' of ''a'' modulo ''n'' *The function ''f:'' ''Q''''n'' → ''Q''''n'' defined by ''f(x) = x2'' mod ''n'' is a permutation. The inverse function of ''f'' is: ''f −1(x) = x((p-1)(q-1)+4)/8'' mod ''n''.〔A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, (Handbook of Applied Cryptography ) ISBN 0-8493-8523-7.〕 *For every Blum integer ''n'', -1 has a Jacobi symbol mod ''n'' of +1, although -1 is not a quadratic residue of ''n'': : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Blum integer」の詳細全文を読む スポンサード リンク
|